import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] array={1,6,7,8,5,4,3,45,6,73,3,4};
        new MergeSort().mergesort(array);
        System.out.println(Arrays.toString(array));
    }

    void mergesort(int[] array){
        //返回条件
        if(array.length<=1){
            return;
        }
        //分解数组
        int leftLength = array.length/2;
        int rightLength = array.length-leftLength;
        int i=0,l=0,r=0;
        int[] leftarray=new int[leftLength];
        int[] rightarray=new int[rightLength];
        while(i<array.length){
            while(l<leftLength){
                leftarray[l++]=array[i++];
            }
            while(r<rightLength){
                rightarray[r++]=array[i++];
            }
        }
        //递归分解
        mergesort(leftarray);
        mergesort(rightarray);
        //有序合并
        merge(leftarray,rightarray,array);
    }

    void merge(int[] leftarray,int[] rightarray,int[] array){
        int i=0,l=0,r=0;
        while(l<leftarray.length && r<rightarray.length){
            if(leftarray[l]<=rightarray[r]){
                array[i++]=leftarray[l++];
            }else{
                array[i++]=rightarray[r++];
            }
        }
        //处理剩余元素
        //触发条件是l=leftSize,或者r=rightSize
        while(l<leftarray.length){
            array[i++]=leftarray[l++];
        }
        while(r<rightarray.length){
            array[i++]=rightarray[r++];
        }
    }
}
